<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<!-- saved from url=(0083)http://celene.univ-orleans.fr/pluginfile.php/152167/mod_resource/content/1/p2p.html -->
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="fr" lang="fr"><head><meta http-equiv="Content-Type" content="text/html; charset=UTF-8">

<title>Projet d'algorithmique répartie — Erlang, de peer en peer !</title>
<style type="text/css" media="all">
#pied {
    font-size: 80%;    
    text-align: right;
    font-style: italic;
}

.toc { 
    font-size: 80%;
    position: fixed;
    top: 1em;
    right: 1em;
    width: 15em;
    background-color: #eee;
    margin: 0px;
    padding: 0px 
    -moz-border-radius: 0.6em;
    border-radius: 0.6em;
}      

.toc ul {
    list-style-type: none;
    padding: 0em 1em;
}

.toc ul ul {
    font-size: 90%;
}

#tour {
    display: inline-block;
    text-align: justify;
    width: 60em;
    padding: 2em;
}

body {
	font: normal 12pt sans-serif;
    line-height: 1.3em;
	text-align: left;
	margin: 3em;
	padding: 2em;
}

#header h2 {
    font-weight: normal;
    font-style: italic;
}

#body h3 {
    margin-top: 3em;
}

#body h1 {
    border-bottom: 1px solid black;
    padding-bottom: 0.25em;
	margin-top: 2em;
}

a {
    color: #ee7700;
    font-weight: bold;
	text-decoration: none;
}

.toc a {
    color: black;
}

blockquote {
	margin-left: 5em;
	margin-top:2em;
	font-style:italic;
}

hr {
	margin-top:3em;
}

pre {
    padding: 1em;
    background-color: #fce4cc;
    -moz-border-radius: 0.6em;
    border-radius: 0.6em;
}
</style>
<style type="text/css" media="print">
body {
    font-size: 10pt
}
.toc, #pied {
    display: none;
}
</style>
<style type="text/css"></style></head>
<body>
<div id="tour">
<div id="header">
<h1>Projet d'algorithmique répartie — Erlang, de peer en peer !</h1>
<h2>M1 informatique, Algorithmique répartie</h2>
<h3>5 avril 2013</h3>
</div>
<div id="corps">
<div class="body" id="body">
<p>
Le but de ce projet est de découvrir les tables de hachage distribuées en développant un système pair à pair décentralisé.
</p>
<p>
Le projet est à réaliser en trinôme, dont la composition est à enregistrer auprès du chargé de TD au début du projet en échange d'un numéro de groupe.
</p>

<h1>1. Nœuds Erlang et Jinterface</h1>

<p>
Cette section présente quelques éléments complémentaires d'Erlang avant d'attaquer le projet.
</p>

<h2>Nœuds</h2>

<p>
Il est possible en Erlang de distribuer les processus sur différents nœuds, des machines virtuelles Erlang qui peuvent être sur la même machine ou sur des machines distantes. Les processus distants sont manipulés comme des processus locaux, de manière transparente pour l'utilisateur. Pour établir un premier contact, il convient de nommer les nœuds et d'enregistrer (c'est à dire de donner un nom à) un processus.
</p>
<p>
Ainsi, dans un premier terminal on peut créer un nœud nommé <code>alice@localhost</code> :
</p>

<pre>$ erl -sname alice@localhost
Erlang R15B03 (erts-5.9.3) [source] [64-bit] [smp:4:4] [async-threads:0] [hipe] [kernel-poll:false]

Eshell V5.9.3  (abort with ^G)
(alice@localhost)1&gt;
</pre>

<p>
Et dans un second terminal un nœud <code>bob@localhost</code> :
</p>

<pre>$ erl -sname bob@localhost
Erlang R15B03 (erts-5.9.3) [source] [64-bit] [smp:4:4] [async-threads:0] [hipe] [kernel-poll:false]

Eshell V5.9.3  (abort with ^G)
(bob@localhost)1&gt; 
</pre>

<p>
On peut vérifier avec <code>net_adm:ping/1</code> que l'autre nœud est bien accessible :
</p>

<pre>(alice@localhost)1&gt; net_adm:ping('bob@localhost').
pong
</pre>

<p>
On enregistre le processus courant :
</p>

<pre>(bob@localhost)1&gt; register(ici, self()).
true
</pre>

<p>
On envoie un message depuis l'autre nœud :
</p>

<pre>(alice@localhost)2&gt; {ici, 'bob@localhost'} ! {self(), ping}. 
{&lt;0.37.0&gt;,ping}
</pre>

<p>
On récupère le message et on répond :
</p>

<pre>(bob@localhost)2&gt; receive {Who, ping} -&gt; ping end.
ping
(bob@localhost)3&gt; Who ! pong.
pong
(bob@localhost)4&gt; Who.
&lt;6774.37.0&gt;
</pre>

<p>
La réponse est bien reçue :
</p>

<pre>(alice@localhost)3&gt; flush().
Shell got pong
ok
</pre>

<p>
Parcourir <a href="http://www.erlang.org/doc/getting_started/conc_prog.html">Concurrent Programming in Erlang</a> pour en savoir davantage sur les nœuds Erlang.
</p>

<h2>Jinterface</h2>

<p>
<a href="http://www.erlang.org/doc/apps/jinterface/jinterface_users_guide.html">Jinterface</a> est un mécanisme qui permet une interaction entre Erlang et Java en créant des nœuds en Java. Dans ce projet, Java sera utilisé pour créer une interface graphique pour déboguer et illustrer le principe de fonctionnement de l'algorithme étudié.
</p>
<p>
Lire la documentation <a href="http://www.erlang.org/doc/apps/jinterface/jinterface_users_guide.html">The Jinterface Package</a>.
</p>
<p>
Puis, écrire, compiler et tester un programme Java qui se comporte comme un nœud <code>java@localhost</code> qui sur la boîte <code>pingpong</code> ignore tout message sauf <code>{Who, ping}</code> auquel il répond en envoyant <code>pong</code> au processus <code>Who</code>.
</p>

<pre>(bob@localhost)5&gt; {pingpong, 'java@localhost'} ! {self(), ping}.
{&lt;0.37.0&gt;,ping}
(bob@localhost)6&gt; flush().
Shell got pong
ok
</pre>

<h1>2. Chord</h1>

<p>
Le cœur du projet consiste en la mise en œuvre de l'algorithme de table de hachage distribuée <a href="http://en.wikipedia.org/wiki/Chord_%28peer-to-peer%29">Chord</a>. Cet algorithme est décrit en détail dans l'article suivant, qu'il vous appartient de lire et de comprendre : <a href="http://pdos.csail.mit.edu/papers/chord:sigcomm01/chord_sigcomm.pdf">Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications</a>. 
</p>
<p>
Une <a href="http://fr.wikipedia.org/wiki/Table_de_hachage">table de hachage</a> est une structure de donnée qui stocke des valeurs indexées par des clés. Une <a href="http://en.wikipedia.org/wiki/Distributed_hash_table">table de hachage distribuée</a> répartie les données entre plusieurs processus, si possible de manière équilibrée, en permettant à tout processus de retrouver une donnée à partir de sa clé (<code>get/1</code>) et de stocker une donnée dans la table (<code>put/2</code>), généralement par le biais d'une fonction de recherche du processus responsable d'une clé donnée (<code>lookup/1</code>).
</p>
<p>
Le principe de répartition de l'algorithme est simple : chaque processus est muni d'un identifiant et chaque valeur stockée dans la table est associée à une clé. On applique une fonction de hachage aux identifiants et on organise les processus en un anneau unidirectionnel suivant les identifiants croissants. Les données sont stockées dans le premier processus dont le hachage de l'identifiant est plus grand que celui de la clé. Pour retrouver une donnée dont on connaît la clé à partir de n'importe quel processus, il suffit de se déplacer dans l'anneau jusqu'à ce que le hachage de l'identifiant du processus soit plus grand que celui de la clé.
</p>
<p>
Dans ce projet, les processus sont des processus Erlang enregistrés (avec <code>register/2</code>), leurs identifiants consistent en une paire <code>{Name, Node}</code> valide pour l'envoi de message vers d'autres nœuds et la fonction de hachage utilisée est SHA1 accessible à travers <code>crypto:sha/1</code> (à qui on fournira la sortie de <code>term_to_binary/1</code> qui se chargera de convertir n'importe quelle valeur Erlang en une suite binaire portable et hachable).
</p>

<h2>Jalon 1. Simple lookup</h2>

<p>
Dans un premier temps, on considère un anneau de processus statique qui mettent chacun en œuvre les trois primitives <code>lookup/1</code>, <code>get/1</code> et <code>put/2</code>. Chaque processus connaît donc son propre identifiant et l'identifiant du suivant sur l'anneau. Les primitives fonctionnent comme suit :
</p>

 <ul>
 <li><code>lookup/1</code> fonctionne par <i>simple lookup</i>: étant donnée en entrée une clé hachée, elle retourne l'identifiant de son successeur si la clé hachée est comprise entre son identifiant haché et celui de son successeur ou invoque la primitive <code>lookup/1</code> du successeur dans le cas contraire ;
 </li>
 <li><code>get/1</code> utilise <code>lookup/1</code> pour identifier le processus responsable d'une clé reçue en entrée puis le contacte pour obtenir la valeur associée ;
 </li>
 <li><code>put/2</code> utilise <code>lookup/1</code> pour identifier le processus responsable d'une clé reçue en entrée et le contacte pour stocker la valeur associée reçue elle aussi en entrée.
 </li>
 </ul>

<p>
Écrire une fonction de création d'anneau qui prend en paramètre une liste de noms de processus, crée l'anneau, enregistre et lance les processus.
</p>
<p>
Ajouter un système de journalisation (<i>log</i>) qui enregistre dans un fichier l'ensemble des invocations de primitives et les messages éhangés entre les processus. Les processus seront nommés par lerus identifiants, accompagnés du haché. Pour obtenir un nom de fichier de journal unique, on pourra utiliser <code>date/0</code> et <code>time/0</code>. On utilisera des horloges virtuelles pour assurer un bon ordonnancement des messages. Le fichier journal doit se remplir au fur et à mesure que l'on est sûr de ne pas avoir manqué de message et non pas uniquement à la fin de l'exécution.
</p>
<p>
Écrire un programme de visualisation en Java qui reçoit un premier message avec la liste des paires (identifiant, identifiant haché), dessine un cercle sur lequel les processus sont positionnés en fonction de leur identifiant haché. Modifier les sources Erlang pour permettre une visualisation élémentaire des opérations réalisées : messages échangés lors d'un <code>lookup/1</code>, récupération avec <code>get/1</code>, dépôt avec <code>put/2</code>.
</p>

<h2>Jalon 2. Scalable lookup</h2>

<p>
Ajouter au jalon précédent une recherche logarithmique en enrichissant chaque processus d'une <i>finger table</i> dont la taille <i>m</i> est paramétrable. La fonction de création reçoit ce paramètre en plus de la liste.
</p>
<p>
Mettre à jour le système de journalisation.
</p>
<p>
Modifier le programme de visualisation pour y afficher les raccourcis pris lors des recherches.
</p>

<h2>Jalon 3. Join and stabilize</h2>

<p>
Dans un réseau P2P, les processus peuvent rejoindre ou quitter la table de hachage à chaque instant. Chord propose une solution algorithmique découpée en jointure et stabilisation que vous allez mettre en œuvre.
</p>
<p>
Modifier en profondeur le jalon précédent pour que chaque processus puisse être créé séparément et répondent aux messages <code>join/1</code> pour rejoindre un anneau dont on connait l'identifiant d'un participant et <code>leave/0</code> pour quitter l'anneau. Les processus exécuteront périodiquement l'algorithme de stabilisation décrit dans l'article.
</p>
<p>
Mettre à jour le système de journalisation.
</p>
<p>
Modifier en conséquence le programme de visualisation pour y voir au moins les arrivées et les départs et l'équilibrage de la prise en charge des clés.
</p>

<h2>Jalon 4. Failure and replication</h2>

<p>
Un bon réseau P2P doit être capable de gérer les défaillances et répliquer les données pour ne pas (trop) en perdre lorsque des processus quittent la table de hachage.
</p>
<p>
Modifier le jalon précédent pour que chaque processus mémorise un nombre paramétrable de <i>r</i> successeurs au lieu d'un seul et réplique les données dont il a la charge sur <i>k</i> processus consécutifs. Les paramètres <i>r</i> et <i>k</i> sont supposés identiques sur tout l'anneau et sont passés en paramètre à la création d'un noeud.
</p>
<p>
Mettre à jour le système de journalisation.
</p>
<p>
Modifier en conséquence le programme de visualisation pour y voir les données dupliquées. Expérimenter la robustesse de cette méthode de stockage.
</p>

<h1>3. P2P</h1>

<p>
Une fois la distribution des données assurée par la table de hachage distribuée, il ne reste plus qu'à spécifier comment les fichiers sont stockées dans cette table pour obtenir un système P2P.
</p>

<h2>Jalon 5. Blocks and meta-data</h2>

<p>
Pour équilibrer la charge entre les processus, on décide de stocker les fichiers à travers la table de hachage sous forme d'une succession de blocs de 64Ko.
</p>
<p>
Proposer une représentation des fichiers dans la table de hachage distribuée. A priori, il existe deux types de données stockées : les blocs qui composent les fichiers eux-mêmes et les méta-données qui associent à un nom de fichier la liste des blocs associés.
</p>
<p>
Ajouter aux processus de l'anneau des primitives <code>getfile/1</code> et <code>putfile/2</code> pour lire et écrire des fichiers dans la table de hachage.
</p>
<p>
Mettre à jour le système de journalisation.
</p>
<p>
Modifier en conséquence le programme de visualisation pour y voir les opérations sur les fichiers, leurs méta-données et leurs blocs de données.
</p>

<h2>Jalon 6. Pour quelques dollars de plus</h2>

<p>
Ajouter une fonction de recherche de fichiers et une interface client textuelle type <code>ftp</code> qui permette de se connecter à un processus et d'échanger avec lui à travers des commandes <code>ls</code>, <code>get</code> et <code>put</code>.
</p>

<h1>Modalités d'évaluation</h1>

<p>
<b>Travail demandé :</b> une archive <code>p2p.tar.gz</code> contenant :
</p>

 <ul>
 <li><code>jalonX/gui/</code> répertoire contenant pour chaque jalon le code source de l'interface utilisateur en Java ;
 </li>
 <li><code>jalonX/erl/</code> répertoire contenant jour chaque jalon le code source Erlang ;
 </li>
 <li><code>jalonX/Makefile</code> un fichier Makefile par jalon pour compiler l'ensemble des sources Java et Erlang ;
 </li>
 <li><code>README</code> un court fichier texte décrivant comment utiliser le logiciel produit ;
 </li>
 <li><code>rapport.t2t</code>, au format <a href="http://txt2tags.org/">txt2tags</a>, expliquant votre code et les choix mis en œuvre.
 </li>
 </ul>

<p>
L'archive est à envoyer par courrier électronique à l'adresse <code>Nicolas.Ollinger@univ-orleans.fr</code> avec comme sujet <code>[algorep] retour projet</code>. N'oubliez pas d'indiquer votre groupe dans le mail et dans le fichier <code>rapport.t2t</code>.
</p>
<p>
La date limite d'envoi du mail est lundi 20 mai 2013 à 23h59.
</p>

<h1>Références</h1>

 <ul>
 <li><a href="http://www.erlang.org/doc/getting_started/conc_prog.html">Concurrent Programming in Erlang</a> ;
 </li>
 <li><a href="http://www.erlang.org/doc/apps/jinterface/jinterface_users_guide.html">The Jinterface Package</a> ;
 </li>
 <li><a href="http://erlang.org/doc/man/crypto.html">Erlang crypto Module</a> ;
 </li>
 <li><a href="http://fr.wikipedia.org/wiki/P2p">P2P (wikipedia)</a> ;
 </li>
 <li><a href="http://en.wikipedia.org/wiki/Chord_%28peer-to-peer%29">Chord (wikipedia)</a> ;
 </li>
 <li><a href="http://pdos.csail.mit.edu/papers/chord:sigcomm01/chord_sigcomm.pdf">Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications</a>.
 </li>
 </ul>

</div>
<!-- xhtml code generated by txt2tags 2.6. (http://txt2tags.org) -->
<!-- cmdline: txt2tags p2p.t2t -->
</div>
<div id="pied">
Dernière modification le 05 April 2013
</div>
</div>



<autoscroll_cursor hidden="" class="vertical"></autoscroll_cursor><div id="window-resizer-tooltip" style="display: block;"><a href="http://celene.univ-orleans.fr/pluginfile.php/152167/mod_resource/content/1/p2p.html#" title="Edit settings" style="background-image: url(chrome-extension://kkelicaakdanhinjdeammmilcgefonfh/images/icon_19.png);"></a><span class="tooltipTitle">Window size: </span><span class="tooltipWidth" id="winWidth">1366</span> x <span class="tooltipHeight" id="winHeight">744</span><br><span class="tooltipTitle">Viewport size: </span><span class="tooltipWidth" id="vpWidth">1366</span> x <span class="tooltipHeight" id="vpHeight">609</span></div></body></html>